package b1_binarytree;
/**
 * 基础二叉树的实现
 */
public class MyBinTree {
    /** 使用左右孩子表示法 **/
    private static class TreeNode {
        char val;
        TreeNode left;
        TreeNode right;
        TreeNode(char val) {
            this.val = val;
        }
    }

    /** 创建二叉树，返回根节点 **/
    public static TreeNode build() {
        TreeNode nodeA = new TreeNode('A');
        TreeNode nodeB = new TreeNode('B');
        TreeNode nodeC = new TreeNode('C');
        TreeNode nodeD = new TreeNode('D');
        TreeNode nodeE = new TreeNode('E');
        TreeNode nodeF = new TreeNode('F');
        TreeNode nodeG = new TreeNode('G');
        TreeNode nodeH = new TreeNode('H');
        nodeA.left = nodeB;
        nodeA.right = nodeC;
        nodeB.left = nodeD;
        nodeB.right = nodeE;
        nodeC.right = nodeF;
        nodeE.left = nodeG;
        nodeG.right = nodeH;
        return nodeA;
    }

    /**
     * 前序遍历：根左右
     * 传入一颗二叉树的根节点，就可以按照先序遍历的方式来输出节点值
     */
    public static void prevOrder(TreeNode root) {
        //边界条件
        if(root == null){
            return;
        }
        //先输出根节点
        System.out.print(root.val + " ");
        // 按照先序遍历的方式递归访问左子树
        prevOrder(root.left);
        // 按照先序遍历的方式递归访问右子树
        prevOrder(root.right);
    }
    //中序遍历：左根右
    public static void inOrder(TreeNode root) {
        if(root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
    //后序遍历：左右根
    public static void postOrder(TreeNode root) {
        if(root == null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

    /** 返回二叉树的节点数 **/
    public static int getNodes(TreeNode root) {
        if(root == null){
            return 0;
        }
        return 1 + getNodes(root.left) + getNodes(root.right);
    }

    /** 返回二叉树的叶子节点数 **/
    public static int getLeafNodes(TreeNode root) {
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        return getLeafNodes(root.left) + getLeafNodes(root.right);
    }

    /** 判断该二叉树是否有val元素 **/
    public static boolean contains(TreeNode root, char val) {
        if(root == null){
            return false;
        }
        if(root.val == val){
            return true;
        }
        return contains(root.left,val) || contains(root.right,val);
    }

    /** 返回该二叉树的深度 **/
    public static int height(TreeNode root) {
        if(root == null){
            return 0;
        }
        return 1 + Math.max(height(root.left),height(root.right));
    }

    /** 返回该二叉树k层的节点数 **/
    public static int getKLevelNodes(TreeNode root,int k) {
        if(root == null || k<=0 || k > height(root)){
            return 0;
        }
        if(k == 1){
            return 1;
        }
        return getKLevelNodes(root.left,k-1) + getKLevelNodes(root.right,k-1);
    }

    //测试
    public static void main(String[] args) {
        //先创建一个二叉树
        TreeNode root = build();

        System.out.print("前序遍历：");
        prevOrder(root);
        System.out.println();
        System.out.print("中序遍历：");
        inOrder(root);
        System.out.println();
        System.out.print("后序遍历：");
        postOrder(root);
        System.out.println();

        System.out.println("该二叉树中的节点数为：" + getNodes(root));

        System.out.println("该二叉树中的叶子节点数为：" + getLeafNodes(root));

        System.out.println(contains(root,'G'));
        System.out.println(contains(root.left,'F'));

        System.out.println("该二叉树的高度为：" + height(root));

        System.out.println("该二叉树第3层的节点数：" + getKLevelNodes(root,3));
    }
}
